package com.zhz.leetcode;

import com.zhz.leetcode.entity.TreeNode;

import java.util.*;

/**
 * 101. 对称二叉树
 * <p>
 * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
 * <p>
 * 示例 1：
 * 输入：root = [1,2,2,3,4,4,3]
 * 输出：true
 * <p>
 * 示例 2：
 * 输入：root = [1,2,2,null,3,null,3]
 * 输出：false
 * <p>
 * 提示：
 * <p>
 * 树中节点数目在范围 [1, 1000] 内
 * -100 <= Node.val <= 100
 * <p>
 * 进阶：你可以运用递归和迭代两种方法解决这个问题吗？
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/symmetric-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class SymmetricTree101 {

    public static void main(String[] args) {
        SymmetricTree101 m = new SymmetricTree101();
        TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(2), null), new TreeNode(2, new TreeNode(2), null));
        boolean res = m.isSymmetric1(root);
        System.out.println(res);
    }

    /**
     * 使用双指针 一个往左走，一个往右走    ，如果没有左边的指针往右走时，右边的指针往左走
     */
    public boolean isSymmetric(TreeNode root) {
        return test(root.left, root.right);
    }

    public boolean test(TreeNode start, TreeNode end) {
        if (start == null && end == null) {
            return true;
        }
        if (start == null || end == null) {
            return false;
        }
        return start.val == end.val && test(start.left, end.right) && test(start.right, end.left);
    }

    /**
     * 使用迭代+队列的形式进行比较判断
     */
    public boolean isSymmetric1(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode tmp1 = queue.poll();
            TreeNode tmp2 = queue.poll();
            if (tmp1 == null && tmp2 == null) {
                continue;
            }
            if ((tmp1 == null || tmp2 == null) || (tmp1.val != tmp2.val)) {
                return false;
            }
            queue.offer(tmp1.left);
            queue.offer(tmp2.right);
            queue.offer(tmp1.right);
            queue.offer(tmp2.left);
        }
        return true;
    }


}
